Shearer's inequality or also Shearer's lemma, in

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, is an inequality in

information theory Information theory is the scientific study of the quantification (science), quantification, computer data storage, storage, and telecommunication, communication of information. The field was originally established by the works of Harry Nyquist a ...

relating the

entropy Entropy is a scientific concept, as well as a measurable physical property, that is most commonly associated with a state of disorder, randomness, or uncertainty. The term and the concept are used in diverse fields, from classical thermodynam ...

of a set of variables to the entropies of a collection of subsets. It is named for mathematician James B. Shearer. Concretely, it states that if ''X''₁, ..., ''X''_''d'' are

random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...

s and ''S''₁, ..., ''S''_''n'' are subsets of such that every integer between 1 and ''d'' lies in at least ''r'' of these subsets, then :

H X_1,\dots,X_d) \leq \frac\sum_^n H X_j)_/math>

where H is entropy and (X_)_is the

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ti ...

of random variables

X_

with indices ''j'' in

S_

Combinatorial version

Let

\mathcal

be a family of subsets of (possibly with repeats) with each

i\in /math> included in at least t members of \mathcal . Let \mathcal be another set of subsets of \mathcal F . Then \mathcal , \mathcal, \leq \prod_\operatorname_(\mathcal)^where \operatorname_(\mathcal)=\ the set of possible intersections of elements of \mathcal with F .

References

{{DEFAULTSORT:Shearer's Inequality Information theory Inequalities

Combinatorial version

See also

References